package com.yww.algorithm.recursion;

/**
 * @author yww
 * @description 递归冒泡排序
 * @since 2024/1/31 12:03
 */
public final class BubbleSort {
    public static void sort(int[] arr) {
        bubble2(arr, 0, arr.length - 1);
    }

    /**
     * 将数组从low到high进行有序排序（未优化）
     *
     * @param arr  待排序数组
     * @param low  开始排序索引
     * @param high 结束排序索引
     **/
    private static void bubble1(int[] arr, int low, int high) {
        if (low == high) { // 结束条件
            return;
        }
        for (int i = low; i < high; i++) {
            if (arr[i] > arr[i + 1]) { // 无序，交换
                swap(arr, i, i + 1);
            }
        }
        bubble1(arr, low, high - 1); // high 缩小
    }

    /**
     * 将数组从low到high进行有序排序（优化）
     *
     * @param arr  待排序数组
     * @param low  开始排序索引
     * @param high 结束排序索引
     **/
    private static void bubble2(int[] arr, int low, int high) {
        if (low == high) { // 结束条件
            return;
        }
        int j = low; // j 作为无序边界，如：有序 j 无序
        for (int i = low; i < high; i++) {
            if (arr[i] > arr[i + 1]) { // 无序，交换
                swap(arr, i, i + 1);
                j = i;
            }
        }
        bubble2(arr, low, j);// 递归从 [low,j] 进行排序
    }


    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
